import java.util.Arrays;


public class TextSearch {
	public static int[] failure(String p) {
		int[] result = new int[p.length()];
		result[0] = -1;
		if((p.length()) == 1) {
			return result;
		}
		result[1] = 0;

		int pIndex = 2;
		int subIndex = 0;
		while(pIndex < p.length()) {
			
			if(p.charAt(pIndex - 1) == p.charAt(subIndex)) {
				result[pIndex] = ++subIndex;
				pIndex++;
			}
			else if(subIndex > 0) {
				subIndex = result[subIndex];
			}
			else {
				result[pIndex] = 0;
				pIndex++;
			}
			
		}
		
		return result;
		
	}
	
	public static int kmp(String t, String p) {
		if(t.equals("")) {
			return -1;
		}
		if(p.equals("")) {
			return 0;
		}
		int[] failureTable = failure(p);
		for(int tIndex = 0; tIndex < t.length(); tIndex++) {
			boolean matched = true;
			System.out.println(t);
			for(int pIndex = 0; pIndex < p.length(); pIndex++)	{
				//----debug
				
				for(int i = 0; i < tIndex; i++) {
					System.out.print(" ");
				}
				System.out.println(p);
				for(int i = 0; i < tIndex+pIndex; i++) {
					System.out.print(" ");
				}
				System.out.println("^");
				//----debug
				
				
				//if matched, skip
				if(t.charAt(tIndex + pIndex) == p.charAt(pIndex)) {
					continue;
				}
				//if mismatched;
				else { 
					int prefixIndex = failureTable[pIndex];
					if(prefixIndex == -1) {
						System.out.println("*pref = 1");
						matched = false;
						break;
					}
					else if(prefixIndex == 0) {
						System.out.println("*pref = 0");
						matched = false;
						tIndex += pIndex-1;
						break;
					}
					else {
						System.out.println("*pref = "+prefixIndex);
						tIndex += pIndex-prefixIndex;
						pIndex = prefixIndex-1;
					}
				}
			}
			
			if(matched) {
				return tIndex;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		System.out.println("  a, b, c, d, a, b, d, a , m");
		System.out.println(Arrays.toString(failure("ABAAABAAMN")));
		System.out.println(kmp("ABC ABCDAB ABCDABCDABDE","ABCDABD"));
	}
}
